package com.dubious.interview.euler;

import static java.util.Arrays.asList;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class Problem24
{
    /**
     * A permutation is an ordered arrangement of objects. For example, 3124 is one possible 
     * permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically 
     * or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 
     * and 2 are:
     * 
     * 012   021   102   120   201   210
     * 
     * What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 
     * 9?
     */
    public static List<Integer> run(int permutationIndex)
    {
        // strategy: we will not iterate over the numbers
        //     for the ith digit (going left to right), use 10 - i! to determine what the digit should be
        List<Integer> remainingDigits = new LinkedList<Integer>(asList(0,1,2,3,4,5,6,7,8,9));
        List<Integer> digits = new ArrayList<Integer>(10);
        // tracks our approach to the one millionth permutation
        int value = 1;
        while(remainingDigits.size() > 0)
        {
            int increment = factorial(remainingDigits.size() - 1);
            int index = 0;
            while(index < remainingDigits.size() - 1 && (value + increment) <= permutationIndex)
            {
                value += increment;
                index++;
            }
            
            digits.add(remainingDigits.remove(index));
        }
        
        return digits;
    }
    
    private static int factorial(int n)
    {
        int factorial = 1;
        for(int i = 2; i <= n; i++)
        {
            factorial *= i;
        }
        
        return factorial;
    }
}